Commands relating to combinatorics and number theory begin with the k key prefix.
The k g (calc-gcd)
[gcd] command computes the Greatest Common Divisor
of two integers. It also accepts fractions; the GCD of two
fractions is defined by taking the GCD of the numerators, and the
LCM of the denominators. This definition is consistent with the
idea that ‘a /
gcd(a,x)’ should yield an integer for any
‘a’ and
‘x’. For other
types of arguments, the operation is left in symbolic form.
The k l (calc-lcm)
[lcm] command computes the Least Common Multiple of
two integers or fractions. The product of the LCM and GCD of two
numbers is equal to the product of the numbers.
The k E
(calc-extended-gcd) [egcd] command
computes the GCD of two integers ‘x’ and ‘y’ and returns a vector
‘[g, a, b]’
where
‘g = gcd(x,y) = a x + b
y’.
The !
(calc-factorial) [fact] command
computes the factorial of the number at the top of the stack. If
the number is an integer, the result is an exact integer. If the
number is an integer-valued float, the result is a floating-point
approximation. If the number is a non-integral real number, the
generalized factorial is used, as defined by the Euler Gamma
function. Please note that computation of large factorials can be
slow; using floating-point format will help since fewer digits
must be maintained. The same is true of many of the commands in
this section.
The
k d (calc-double-factorial)
[dfact] command computes the “double
factorial” of an integer. For an even integer, this is the
product of even integers from 2 to ‘N’. For an odd integer, this is the
product of odd integers from 3 to ‘N’. If the argument is an
integer-valued float, the result is a floating-point
approximation. This function is undefined for negative even
integers. The notation ‘N!!’ is also recognized for double
factorials.
The k c
(calc-choose) [choose] command computes
the binomial coefficient ‘N’-choose-‘M’, where ‘M’ is the number on the top of the
stack and ‘N’
is second-to-top. If both arguments are integers, the result is
an exact integer. Otherwise, the result is a floating-point
approximation. The binomial coefficient is defined for all real
numbers by
‘N! / M!
(N-M)!’.
The H k c
(calc-perm) [perm] command computes the
number-of-permutations function ‘N! / (N-M)!’.
The k b
(calc-bernoulli-number) [bern] command
computes a given Bernoulli number. The value at the top of the
stack is a nonnegative integer ‘n’ that specifies which Bernoulli
number is desired. The H k b command computes a
Bernoulli polynomial, taking ‘n’ from the second-to-top position and
‘x’ from the
top of the stack. If ‘x’ is a variable or formula the result
is a polynomial in ‘x’; if ‘x’ is a number the result is a
number.
The k e
(calc-euler-number) [euler] command
similarly computes an Euler number, and
H k e computes an Euler
polynomial. Bernoulli and Euler numbers occur in the Taylor
expansions of several functions.
The k s
(calc-stirling-number) [stir1] command
computes a Stirling number of the first
kind, given two integers ‘n’ and ‘m’ on the stack. The H k s
[stir2] command computes a Stirling number of the
second
kind. These are the number of ‘m’-cycle permutations of
‘n’ objects,
and the number of ways to partition ‘n’ objects into
‘m’ non-empty
sets, respectively.
The k p
(calc-prime-test) command checks if the integer on
the top of the stack is prime. For integers less than eight
million, the answer is always exact and reasonably fast. For
larger integers, a probabilistic method is used (see Knuth vol.
II, section 4.5.4, algorithm P). The number is first checked
against small prime factors (up to 13). Then, any number of
iterations of the algorithm are performed. Each step either
discovers that the number is non-prime, or substantially
increases the certainty that the number is prime. After a few
steps, the chance that a number was mistakenly described as prime
will be less than one percent. (Indeed, this is a worst-case
estimate of the probability; in practice even a single iteration
is quite reliable.) After the k p command, the number
will be reported as definitely prime or non-prime if possible, or
otherwise “probably” prime with a certain probability
of error.
The normal k p command performs one iteration of the primality test. Pressing k p repeatedly for the same integer will perform additional iterations. Also, k p with a numeric prefix performs the specified number of iterations. There is also an algebraic function ‘prime(n)’ or ‘prime(n,iters)’ which returns 1 if ‘n’ is (probably) prime and 0 if not.
The k f
(calc-prime-factors) [prfac] command
attempts to decompose an integer into its prime factors. For
numbers up to 25 million, the answer is exact although it may
take some time. The result is a vector of the prime factors in
increasing order. For larger inputs, prime factors above 5000 may
not be found, in which case the last number in the vector will be
an unfactored integer greater than 25 million (with a warning
message). For negative integers, the first element of the list
will be -1. For inputs -1, 0, and 1,
the result is a list of the same number.
The k
n (calc-next-prime) [nextprime]
command finds the next prime above a given number. Essentially,
it searches by calling calc-prime-test on successive
integers until it finds one that passes the test. This is quite
fast for integers less than eight million, but once the
probabilistic test comes into play the search may be rather slow.
Ordinarily this command stops for any prime that passes one
iteration of the primality test. With a numeric prefix argument,
a number must pass the specified number of iterations before the
search stops. (This only matters when searching above eight
million.) You can always use additional k p commands
to increase your certainty that the number is indeed prime.
The I k
n (calc-prev-prime) [prevprime]
command analogously finds the next prime less than a given
number.
The k t
(calc-totient) [totient] command
computes the Euler “totient”
function, the number of integers less than
‘n’ which are
relatively prime to ‘n’.
The k m
(calc-moebius) [moebius] command
computes the
Moebius “mu” function. If the input number is a
product of ‘k’
distinct factors, this is ‘(-1)^k’. If the input number has any
duplicate factors (i.e., can be divided by the same prime more
than once), the result is zero.